package Other.DP;

/**
 * @author:gao
 * @date:2020/7/14
 * @time:13:38
 * @version:0.0.1
 * @description:none
 */

//152. 乘积最大子数组
public class MaxProduct {
}

class SolutionMaxProduct {
    public int maxProduct(int[] nums) {
        int length = nums.length;
        int max = nums[0];
        int dp_min[] = new int[length];
        int dp_max[] = new int[length];
        dp_max[0] = dp_min[0] = nums[0];
        for(int i = 1; i < length; i++){
            dp_max[i] = Math.max(dp_max[i-1]*nums[i], Math.max(dp_min[i-1]*nums[i], nums[i]));
            dp_min[i] = Math.min(dp_min[i-1]*nums[i], Math.min(dp_max[i-1]*nums[i], nums[i]));
            max = Math.max(max, dp_max[i]);
        }
        return max;
    }
}